class main{
    public int[][] insert(int[][] intervals, int[] newInterval) {
        ArrayList<int[]> res=new ArrayList<>();
        int i=0;
        while(i<intervals.length&&newInterval[0]>intervals[i][1]){
            res.add(intervals[i]);
            i++;
        }
        int left=newInterval[0];
        if(i<intervals.length){
            left=Math.min(intervals[i][0],newInterval[0]);
        }
        int right=newInterval[1];
        while(i<intervals.length&&newInterval[1]>=intervals[i][0]){
            i++;
        }
        if(i>0) right=Math.max(right,intervals[i-1][1]);
        res.add(new int[]{left,right});
        while(i<intervals.length){
            res.add(intervals[i]);
            i++;
        }
        
        int ans[][]=new int[res.size()][2];
        for(int j=0;j<res.size();j++){
            ans[j]=res.get(j);
        }
        return ans;
    }
}